package tree

import "algorithm/common"

/*
求二叉树的深度
*/
func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l := MaxDepth(root.Left)
	r := MaxDepth(root.Right)
	return common.Max(l, r) + 1
}

/*
创建一颗二叉树的镜子二叉树
*/
func MirrorTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	node := new(TreeNode)
	node.Val = root.Val
	if root.Right != nil {
		node.Left = MirrorTree(root.Right)
	}
	if root.Left != nil {
		node.Right = MirrorTree(root.Left)
	}
	return node
}

/*
从一个有序数组创建出一颗高度平衡的二叉树
*/
func sortedArrayToBst(nums []int, s, e int) *TreeNode {
	if e-s < 0 {
		return nil
	}
	node := new(TreeNode)
	middle := s + (e-s)/2
	node.Val = nums[middle]
	if e == s {
		return node
	}
	if e-1 == s {
		right := new(TreeNode)
		right.Val = nums[e]
		node.Right = right
		return node
	}
	left := sortedArrayToBst(nums, s, middle-1)
	right := sortedArrayToBst(nums, middle+1, e)
	node.Left = left
	node.Right = right
	return node
}

/*
从一个有序数组创建出一颗高度平衡的二叉树
*/
func SortedArrayToBST(nums []int) *TreeNode {
	return sortedArrayToBst(nums, 0, len(nums)-1)
}
